package day_2022_12_to_3.year2023;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author haomin
 * @date 2023/01/02 23:24
 **/
public class Day1_2_Num1801 {
    public int getNumberOfBacklogOrders(int[][] orders) {
        //int[] {price,amount} buy大根堆 sell小根堆
        PriorityQueue<int[]> buy=new PriorityQueue<>((a, b)->b[0]-a[0]),sell=new PriorityQueue<>((a, b)->a[0]-b[0]);
        int ans=0,mod=(int)1e9+7;
        for(int[] i:orders){
            int amount=i[1];
            if(i[2]==1){
                while(true){
                    if(buy.isEmpty()) break;
                    int[] t=buy.poll();
                    if(t[0]>=i[0]){
                        if(amount>=t[1]) amount-=t[1];
                        else {
                            buy.add(new int[]{t[0],t[1]-amount});
                            amount=0;
                            break;
                        }
                    }else {
                        buy.add(t);
                        break;
                    }
                }
                if(amount!=0) sell.add(new int[]{i[0],amount});
            }else{
                while(true){
                    if(sell.isEmpty()) break;
                    int[] t=sell.poll();
                    if(t[0]<=i[0]){
                        if(amount>=t[1]) amount-=t[1];
                        else{
                            sell.add(new int[]{t[0],t[1]-amount});
                            amount=0;
                            break;
                        }
                    }else{
                        sell.add(t);
                        break;
                    }
                }
                if(amount!=0) buy.add(new int[]{i[0],amount});
            }
        }
        for(int[] i:buy) ans=(ans+i[1])%mod;
        for(int[] i:sell) ans=(ans+i[1])%mod;
        return ans;
    }
    class Solution2 {
        public static final int MOD = 10_0000_0007;
        public int getNumberOfBacklogOrders(int[][] orders) {
            PriorityQueue<int[]> pqBuy = new PriorityQueue<>(Comparator.<int[]>comparingInt(arr -> arr[0]).reversed());
            PriorityQueue<int[]> pqSell = new PriorityQueue<>(Comparator.comparingInt(arr -> arr[0]));
            for (int[] order : orders)
                if (order[2] == 0)
                    helper(pqBuy, pqSell, order[0], order[1], true);
                else
                    helper(pqSell, pqBuy, order[0], order[1], false);

            int ans = 0;
            List<PriorityQueue<int[]>> list = new LinkedList<>();
            list.add(pqBuy); list.add(pqSell);
            for (PriorityQueue<int[]> pq : list)
                while (!pq.isEmpty())
                    ans = (ans + pq.poll()[1]) % MOD;
            return ans;
        }

        private void helper(PriorityQueue<int[]> from, PriorityQueue<int[]> to, int price, int amount, boolean lessThan) {
            while (amount > 0 && !to.isEmpty() && (lessThan ? to.peek()[0] <= price : to.peek()[0] >= price)) {
                int[] poll = to.poll();
                int min = Math.min(amount, poll[1]);
                amount -= min;
                poll[1] -= min;
                if (0 < poll[1])
                    to.offer(poll);
            }
            if (amount > 0)
                from.offer(new int[]{price, amount});
        }
    }
}